package org.example.day05;

import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * @author zlxad
 * @version 1.0
 * @description: TODO +
 * <p>  一个歌手准备从A城去B城参加演出。 </p> <p>  1)     按照合同，他必须在T天内赶到。 </p> <p>  2)     歌手途径N座城市。 </p> <p>  3)     歌手不能往回走。 </p> <p>  4)     每两座城市之间需要的天数都可以提前获知。 </p> <p>  5)     歌手在每座城市都可以在路边卖唱赚钱。经过调研，歌手提前获知了每座城市卖唱的收入预期： </p> <p>  如果在一座城市第一天卖唱可以赚M，后续每天的收入会减少D（第二天赚的钱是M – D，第三天是M-2D…）。如果收入减到0就不会再少了。 </p> <div>  6)     歌手到达后的第二天才能开始卖唱。如果今天卖过唱，第二天才能出发。 </div> <div>  <br> </div> <p>  贪心的歌手最多可以赚多少钱？ </p>
 * <p>
 * 一个歌手准备从A城去B城参加演出。
 * 1)     按照合同，他必须在T天内赶到。
 * 2)     歌手途径N座城市。
 * 3)     歌手不能往回走。
 * 4)     每两座城市之间需要的天数都可以提前获知。
 * 5)     歌手在每座城市都可以在路边卖唱赚钱。经过调研，歌手提前获知了每座城市卖唱的收入预期：
 * 如果在一座城市第一天卖唱可以赚M，后续每天的收入会减少D（第二天赚的钱是M – D，第三天是M-2D…）。如果收入减到0就不会再少了。
 * 6)     歌手到达后的第二天才能开始卖唱。如果今天卖过唱，第二天才能出发。
 * <p>
 * 贪心的歌手最多可以赚多少钱？
 * @date 2024/3/11 15:22
 */
public class test082 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取总天数T和城市数N
        int T = scanner.nextInt();
        int N = scanner.nextInt();

        // 读取经过每两座城市之间所需的天数
        int[] travelDays = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            travelDays[i] = scanner.nextInt();
        }

        // 读取每座城市的卖唱收入预期M和每天收入减少量D
        int[][] cityEarnings = new int[N][2];
        for (int i = 0; i < N; i++) {
            cityEarnings[i][0] = scanner.nextInt(); // M
            cityEarnings[i][1] = scanner.nextInt(); // D
        }

        // 调用函数计算最大收益并输出结果
        System.out.println(calculateMaxEarnings(T, travelDays, cityEarnings));
    }

    /**
     * 计算最大收益的函数
     *
     * @param T            总天数
     * @param travelDays   每两座城市之间旅行所需的天数
     * @param cityEarnings 每座城市的卖唱收入预期和每天收入减少量
     * @return 最大收益
     */
    public static int calculateMaxEarnings(int T, int[] travelDays, int[][] cityEarnings) {
        // 计算总旅行时间
        int totalTravelTime = 0;
        for (int time : travelDays) {
            totalTravelTime += time;
        }

        // 计算除去旅行时间后的剩余时间
        int remainingTime = T - totalTravelTime;

        // 如果没有剩余时间，则收益为0
        if (remainingTime <= 0) {
            return 0;
        }

        // 使用小顶堆存储每天的收益，以优化收益最大化的过程
        PriorityQueue<Integer> dailyProfits = new PriorityQueue<>();

        // 遍历每座城市，计算在该城市的最大潜在收益
        for (int[] earnings : cityEarnings) {
            int M = earnings[0]; // 初始收益
            int D = earnings[1]; // 每天收益减少量
            int currentDayProfit = M;
            int dayCounter = 0;

            // 当日收益大于0时继续计算
            while (currentDayProfit > 0) {
                // 如果堆中的元素数量小于剩余时间，则直接加入堆中
                if (dailyProfits.size() < remainingTime) {
                    dailyProfits.add(currentDayProfit);
                } else if (currentDayProfit > dailyProfits.peek()) {
                    // 如果当前日收益大于堆顶元素，则替换堆顶元素为当前收益
                    dailyProfits.poll(); // 移除堆顶元素
                    dailyProfits.add(currentDayProfit); // 加入新的收益
                } else {
                    // 如果当前日收益不高于堆顶元素，则结束循环
                    break;
                }

                dayCounter++; // 增加计数器
                currentDayProfit = M - dayCounter * D; // 更新下一天的收益
            }
        }

        // 计算总收益
        int totalEarnings = 0;
        for (int profit : dailyProfits) {
            totalEarnings += profit;
        }

        return totalEarnings;
    }
}


